/*
 * @lc app=leetcode.cn id=547 lang=java
 *
 * [547] 省份数量
 */

// @lc code=start
class Solution {
    // 又是并查集，但使用BFS,DFS也可以
    public int findCircleNum(int[][] isConnected) {
        //事实上访问上面那个表的一半即可，因为是无向边
        int len = isConnected.length;
        boolean[] visited = new boolean[len];//初始值是false
        int ans = 0;
        for(int i =0 ;i<len ;i++){
            if(!visited[i]){
                dfs(isConnected, visited, len, i);
                ans++;
            }
        }
        return ans;
    }
    public void dfs(int[][] isConnected ,boolean[] visited, int len , int i){
        for(int j = 0;j<len ;j++){
            if(!visited[j] && isConnected[i][j]==1){//如果这个点未被访问过，且与i联通，则dfs访问它
                visited[j] = true;
                dfs(isConnected, visited, len, j);
            }
        }
    }
}
// @lc code=end

